package LinkedList;
//现有一链表的头指针 ListNode* pHead，给一定值x，
//编写一段代码将所有小于x的结点排在其余结点之前，
//且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
public class Solution6 {
    public ListNode partition(ListNode pHead, int x) {
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = pHead;
        if(pHead == null){
            return null;
        }
        while (cur != null) {
            if(cur.val<x){
                //判断是否是第一次插入
                if(as == null){
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = cur;
                }
            }else {
                //判断是否是第一次插入
                if(bs == null){
                    bs = cur;
                    be = cur;
                }else {
                    be.next = cur;
                    be = cur;
                }
            }
            cur = cur.next;
        }
        //判断第一区间是否为空
        if(as==null){
            return bs;
        }
        //进行连接
        ae.next = bs;
        //如果后一区间不为空，尾节点的next应置空，避免成环死循环
        if(be!=null){
            be.next = null;
        }
        //返回第一区间的开头节点
        return as;

    }
}
